#include <iostream>
#include <typeinfo>

template <typename T, unsigned N>
struct Constructor
{
  typedef typename Constructor<typename T::_, N - 1>::is is;
};


template <typename T>
struct Constructor<T, 0>
{
  typedef typename T::_ is;
};

template <template <typename> class F>
struct Rec : F< Rec<F> >
{
  typedef F< Rec<F> > _root;
};

/// Helper
///
template <typename T, unsigned N>
struct C
{
  typedef typename Constructor<Rec<T::template __>, N>::is is;
};

/// SlideCs -- calculate depth of nesting 
///
template <typename COUTER, typename CINNER>
struct SlideCs
{
  enum { constructors = SlideCs<CINNER, typename CINNER::_>::constructors + 1 };
};

template <typename COUTER>
struct SlideCs<COUTER, void>
{
  enum { constructors = 1 };
};

/// Cs -- helper template to calculate number of contructors
///
template <typename T>
struct Cs
{
  typedef typename Rec<T::template __>::_ c0;
  enum { is = SlideCs<c0, typename c0::_>::constructors };
};


/// SlideVt -- calculate variant table
///
template <typename COUTER, typename CINNER>
struct SlideVt
{
  struct _
  {
    void (*p)(COUTER&);
    typename SlideVt<CINNER, typename CINNER::_>::_ q;
  };
};

template <typename COUTER>
struct SlideVt<COUTER, void>
{
  struct _
  {
    void (*p)(COUTER&);
  };
};

/// SlideVte -- calculate variant table (environment flavour)
///
template <typename ENV, typename RET, typename COUTER, typename CINNER>
struct SlideVte
{
  typedef RET (*proc)(ENV, COUTER&);
  struct _
  {
    proc p;
    typename SlideVte<ENV, RET, CINNER, typename CINNER::_>::_ q;
    const typename SlideVte<ENV, RET, CINNER, typename CINNER::_>::_& getq(void) const
    {
      return q;
    }
  };
};

template <typename ENV, typename RET, typename COUTER>
struct SlideVte<ENV, RET, COUTER, void>
{
  typedef RET (*proc)(ENV, COUTER&);
  struct _
  {
    proc p;
    const _& getq(void) const
    {
      return *this;
    }
  };
};

/// Vt -- helper template to calculate variant table
///
template <typename T>
struct Vt
{
  typedef typename Rec<T::template __>::_ c0;
  typedef typename SlideVt<c0, typename c0::_>::_ table;
};

/// Vte -- helper template to calculate variant table (environment flavour)
///
template <typename ENV, typename RET, typename T>
struct Vte
{
  typedef typename Rec<T::template __>::_ c0;
  typedef typename SlideVte<ENV, RET, c0, typename c0::_>::_ table;
  ENV e;
  table t;
  Vte(ENV e, const table& t) : e(e), t(t) {}
};


template <typename T>
struct List
{
    unsigned _tag;
  List(unsigned _tag) : _tag(_tag) {}

    typedef struct back
    {
        typedef void _;
        typedef List root;
    } _;

    template <typename> 
    struct __ {
        typedef struct Nil : List
        {
	  Nil(void) : List(1) {}

            typedef struct Cons : List
            {
                T payload;
                List& next;
	      Cons(const T& payload, List& next) : List(2), payload(payload), next(next) {}
                typedef void _;
                typedef List root;
            } _;
        } _;
    };
};

void n0(C<List<int>, 0>::is&)
{
  std::cout << "Nil!" << "\n";
}

void n1(C<List<int>, 1>::is& c)
{
  std::cout << "Cons! " << c.payload << "\n";
}

int n0e(char, C<List<int>, 0>::is&)
{
  std::cout << "Nil!" << "\n";
  return 42;
}

int n1e(char e, C<List<int>, 1>::is& c)
{
  std::cout << "Cons! " << c.payload << " env: " << e << "\n";
  return 42 + e;
}

// TODO: GADTs:
// http://lambdalog.seanseefried.com/posts/2011-11-22-gadts-in-scala.html

template <typename T>
struct Expr
{
  unsigned _tag;
  Expr(unsigned _tag) : _tag(_tag) {}

    typedef struct back
    {
      typedef void _;
      typedef Expr root;
    } _;

  template <typename>
  struct __ {
    typedef struct LitInt : Expr<int>
    {
      int i;
      LitInt(int i) : Expr(1), i(i) {}
      typedef struct LitBool : Expr<bool>
      {
	bool b;
	LitBool(bool b) : Expr(2), b(b) {}
	typedef struct Add : Expr<int>
	{
	  const Expr<int>& lhs;
	  const Expr<int>& rhs;
	  Add(const Expr<int>& lhs, const Expr<int>& rhs) : Expr(3), lhs(lhs), rhs(rhs) {}
	  typedef struct Mul : Expr<int>
	  {
	    const Expr<int>& lhs;
	    const Expr<int>& rhs;
	    Mul(const Expr<int>& lhs, const Expr<int>& rhs) : Expr(4), lhs(lhs), rhs(rhs) {}
	    typedef struct Cond : Expr
	    {
	      bool b;
	      const Expr& thn;
	      const Expr& els;
	      Cond(bool b, const Expr& thn, const Expr& els) : Expr(5), b(b), thn(thn), els(els) {}
	    } _;
	  } _;
	} _;
      } _;
    } _;
  };
};



template <typename T, unsigned N>
void Dispatch(const typename Vt<T>::table& table, typename C<T, N>::is& v)
{
  /// @todo walk inside the table until type matches and call discriminator
  /// @todo when exhausted, loop back to __root's table
}


/// forcer functor
template <typename T>
struct Forcer
{
  /// @todo basically a function pointer that accepts a payload and creates a T
};


/// Representations: create, pointer-encode, force, find GC roots, overwrite, dispose datatypes

/// Exactly as given
template <typename T>
struct Id
{
  typedef T simplify;
  T* create(const T& t)
  {
    return new T(t);
  }
};

/// With thunk
///
template <typename T>
struct Thunk : Forcer<T>, T
{
    Thunk(Forcer<T> f)
    : Forcer<T>(f) {}
    
    typedef Thunk simplify;
    T* create(Forcer<T> f)
    {
        return new Thunk(f);
    }
};


/// @brief provide a common entry to create all possible representations
///
template <typename T, template <typename> class WRAP = Id>
struct Rep
{
  typedef typename WRAP<T>::simplify wrapped;
};

/// Applicative Structs

/// Type system for applicative

template <typename A, typename B, typename C>
struct Same
{
};

template <typename A, typename C>
struct Same<A, A, C>
{
  typedef C simplify;
};

template <typename A, typename B>
struct Arr
{
    typedef Arr<typename A::simplify, typename B::simplify> simplify;
    
    /// modus ponens
    template <typename ARG>
    struct App
    {
        typedef typename Same<typename A::simplify, typename ARG::simplify, typename B::simplify>::simplify simplify;
    };
};

template <typename T, T (*F)(T)>
struct UnaryPrim
{
    template <typename A>
    struct Appl
    {
        static T force();
    };
    
    static UnaryPrim force()
    {
        return UnaryPrim();
    }
};

template <typename CTX, typename T, T (CTX::*F)(T)>
struct UnaryCtx
{
    
};

template <typename T, T (*F)(T, T)>
struct BinPrim
{
    typedef typename Arr<T, typename Arr<T, T>::simplify>::simplify simplify;
    enum { known = true };

    // when arg is known
    template <typename A>
    static T compute(T v)
    {
        return F(A::force(), v);
    }
    
    // when arg is runtime
    struct Ctx
    {
        T keep;
        T compute(T v)
        {
            
        }
    };
    template <typename A>
    struct Appl : UnaryPrim<T, &compute<A> >
    //struct Appl : UnaryCtx<Ctx, T, &Ctx::compute>
    {
        typedef typename BinPrim::simplify::template App<typename A::simplify>::simplify simplify;
        enum { known = true };
    };
};


struct PrimInt {
  typedef PrimInt simplify;
  enum { known = false };
};

struct PrimBool {
  typedef PrimBool simplify;
};

PrimInt operator + (PrimInt, PrimInt)
{
  return PrimInt();
}

typedef BinPrim<PrimInt, operator+> Plus;

template <int I>
struct Int : PrimInt
{
  enum { known = true };
  static simplify force()
  {
    return PrimInt(/*I*/);
  };
};

typedef Int<2> Two;
typedef Int<40> Fourty;

template <typename F, typename A>
struct App
{
    typedef typename F::simplify::template App<A>::simplify simplify;
    enum { known = F::known && A::known };

    /// this implementation is highly dubious
    template <typename A2>
    struct Appl : F::template Appl<A2>
    {
    };
    
    static /*non*/simplify force()
    {
        if (known)
        {
            //return typename F::template Appp<A>();
// ERROR:todo            return F::template Appl<A>::force();
        }
        else
        {
            
        }
    }
};

typedef App<Plus, Two> PlusTwo;
typedef App<PlusTwo, Fourty> T42;


int main (int argc, char * const argv[]) {
    // insert code here...
    std::cout << "Hello, World!\n";

    Rec<List<int>::__> a;
    std::cout << typeid(a).name() << "\n";

    C<List<int>, 0>::is n;
    C<List<int>, 1>::is c(42, n);
    // Constructor<Rec<List>, 2>::is x; // gives desired error: x declared as void
    std::cout << typeid(n).name() << "\n";
    std::cout << typeid(c).name() << " payload: " << c.payload << "\n";

    std::cout << "List<int> has " << Cs<List<int> >::is << " constructors" << "\n";

    Vt<List<int> >::table vt = { n0, n1 };
    vt.p(n);
    vt.q.p(c);

    Dispatch<List<int>, 1>(vt, c);
    
    // test the Applicative stuff
    Fourty::force();
    PlusTwo::force();
    //T42::force();
}

// implement http://code.google.com/p/catatonic/wiki/OperatorArrowStar
// and http://code.google.com/p/catatonic/wiki/CrazyIdeas#Forcing
//

template <typename ENV>
struct Env
{
  template <typename SOFAR, typename RET, typename COUTER, typename CINNER>
  struct cache;

  template <typename RET, typename T>
  cache<Env, RET, typename Vte<ENV, RET, T>::c0, typename Vte<ENV, RET, T>::c0::_>
  operator * (RET (*cf)(ENV, T&))
	{
    typedef typename Vte<ENV, RET, T>::c0 c0;
    typedef typename c0::_ c1;
    typename SlideVte<ENV, RET, c0, c1>::proc cf0(cf);
    return cache<Env, RET, c0, c1>(*this, cf0);
	}

	template <typename U>
  U join(const U& q)
	{
		return q;
	}

	ENV env;
	Env(ENV env) : env(env) {}
	ENV e(void)
	{
		return env;
	}
};

template <typename ENV>
template <typename SOFAR, typename RET, typename COUTER, typename CINNER>
struct Env<ENV>::cache : SOFAR
{
	typedef typename SlideVte<ENV, RET, COUTER, CINNER>::proc proc;
  cache(const SOFAR& s, proc p) : SOFAR(s), p(p) {}
  proc p;
  
  template <typename T>
  cache<cache, RET, CINNER, typename CINNER::_>
  operator * (RET (*cf)(ENV, T&))
	{
    typedef typename CINNER::_ CNEXT;
    typename SlideVte<ENV, RET, CINNER, CNEXT>::proc cfn(cf);
		return cache<cache, RET, CINNER, CNEXT>(*this, cfn);
	}

	typename SlideVte<ENV, RET, COUTER, CINNER>::_
  join(const typename SlideVte<ENV, RET, CINNER, typename CINNER::_>::_& q)
	{
		typename SlideVte<ENV, RET, COUTER, CINNER>::_ is = { p, q };
    return SOFAR::join(is);
	}
};

template <typename ENV>
template <typename SOFAR, typename RET, typename COUTER>
struct Env<ENV>::cache<SOFAR, RET, COUTER, void> : SOFAR
{
	typedef typename SlideVte<ENV, RET, COUTER, void>::proc proc;
  cache(const SOFAR& s, proc p) : SOFAR(s), p(p) {}
  proc p;
  operator Vte<ENV, RET, typename COUTER::root>(void)
	{
		typename SlideVte<ENV, RET, COUTER, void>::_ here = { p };
    return Vte<ENV, RET, typename COUTER::root>(SOFAR::e(), SOFAR::join(here));
	}
};

const Vte<char, int, List<int> > oo(Env<char>('&') * n0e * n1e);


C<List<int>, 0>::is n;
C<List<int>, 1>::is c(42, n);
List<int>& c0(c);

template <typename COUTER, typename CINNER>
struct SlideRoot
{
	typedef typename SlideRoot<CINNER, typename CINNER::_>::is is;
};

template <typename COUTER>
struct SlideRoot<COUTER, void>
{
	typedef typename COUTER::root is;
};


template <typename ENV, typename RET, typename T, typename U, class TAB>
RET callCase(int n, ENV e, T& v, RET (*p)(ENV, U&), const TAB& t)
{
	if (!n)
		{
			typename SlideRoot<T, typename T::_>::is& vb(v);
			return p(e, static_cast<U&>(vb));
		}
	else
		{
			return callCase(n - 1, e, v, t.p, t.getq());
		}
}

const int& ch0(callCase(1, 'k', c0, oo.t.p, oo.t.q));
const int& ch1(callCase(1, 'l', c, oo.t.p, oo.t.q));


template <typename ENV, typename RET, typename T, typename U>
RET operator ->* (/*const*/ T& v, const Vte<ENV, RET, U>& te)
{
	return callCase(1, te.e, v, te.t.p, te.t.getq());
}

const int& ch(c->*oo);

